'''
Created on Aug 12, 2009

@author: Roni
'''
import cliques.cliqueAlgorithm
import cliques.cliqueFinder
class CliqueSearchLowerbound(cliques.cliqueAlgorithm.cliqueAlgorithm):
    '''
    classdocs
    '''


    def __init__(self):
        '''
        Constructor
        '''
        cliques.cliqueAlgorithm.cliqueAlgorithm.__init__(self)
    
    def halt(self):
        return self.clique_found()==True or len(self.generated)==0
    
    def clique_found(self):
        self.done = self.clique_finder.has_clique(self.k,self.ckg.nodes())
        return self.done
        
    def step(self):
        ''' Perform a breadth first search step over all generated nodes '''        
        current_level_nodes = list(self.generated)
        clique_found=False
        while len(current_level_nodes)>0:
            current_node = current_level_nodes.pop()
            self.expand(current_node)

        self.iteration=self.iteration+1
        if self.clique_found():
            self.iteration=self.iteration+self.k-3
            
    def get_cost(self):
        return self.iteration
    def __str__(self):
        return "lowerbound"
